Em teoria dos grafos, coloração de grafos é um caso especial de rotulagem de grafos; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Em sua forma mais simples, é uma forma de colorir os vértices de um grafo tal que não haja dois vértices adjacentes que compartilhem a mesma cor; isso é chamado de uma coloração de vértices. Da mesma forma, uma coloração de arestas atribui uma cor para cada aresta de modo que não haja duas arestas adjacentes da mesma cor, e uma coloração de faces de um grafo planar atribui uma cor para cada face ou região de modo que não haja duas faces que compartilham uma fronteira tendo a mesma cor.

A coloração de vértices é o ponto de partida para o assunto, e outros problemas de coloração podem ser transformados em uma versão de vértices. Por exemplo, uma coloração de arestas de um grafo é simplesmente uma coloração de vértices do seu grafo linha, e uma coloração de face de um grafo planar é apenas uma coloração de vértices do seu dual planar. No entanto, problemas de coloração de não-vértices são muitas vezes referidos e estudado como são. Isso se deve em parte à perspectiva, e em parte porque alguns problemas são mais bem estudados na forma não-vértice, como por exemplo, a coloração de arestas.

A convenção do uso de cores provém de colorir os países de um mapa, onde cada face é literalmente colorida. Este foi generalizado para coloração das faces de um grafo incorporado no plano. Pela dualidade planar se passou a colorir os vértices, e desta forma se generalizou a todos os grafos. Em representações matemáticas e na informática é comum usar os primeiros números inteiros positivos ou não negativos como as "cores". Em geral pode-se usar qualquer conjunto finito como "conjunto de cores". A natureza do problema de coloração depende do número de cores, mas não sobre o que são.

A coloração de grafos goza de muitas aplicações práticas, bem como desafios teóricos. Ao lado dos tipos clássicos de problemas, limitações diferentes também podem ser definidas no grafo, ou na forma como uma cor é atribuída, ou mesmo sobre a própria cor. Ela chegou até a se popularizar com o público em geral na forma da popular série de quebra-cabeças Sudoku. A coloração de grafos ainda é um campo de pesquisa muito ativa.